// 文件名：list_free_list_allocator.cpp
// 目的：实现一个简单的“空闲链表（Free List）”分配器，按偏移升序维护空闲块，支持：
//   - allocate(size, outOffset)：首次适配（First-Fit）策略从前到后查找可用块；
//   - deallocate(offset, size)：释放后按偏移插入并与前后相邻块合并（coalesce）；
//   - dump()：打印当前空闲块分布，便于调试。
// 要点与注意：
//   - 时间复杂度：allocate/deallocate 为 O(n)（n 为空闲块数量）；
//   - 合并策略：仅与“相邻”的前后块合并，减少外部碎片；
//   - 有序插入：deallocate 时按 offset 插入，保证链表始终升序；
//   - 对齐：本示例未处理对齐需求；实际使用中应按对齐向上取整，分配时考虑对齐偏移；
//   - 线程安全：非线程安全；多线程需外部加锁；
//   - 边界检查：调用方需保证 deallocate 的 (offset, size) 合法且与分配记录一致；
//   - 改进方向：支持最佳适配/最差适配、分离空闲列表（按大小分桶）、统计信息等。

#include <list>
#include <iostream>

struct Block {
    std::size_t offset; // 起始偏移
    std::size_t size;   // 块大小
};

class FreeList {
public:
    // 初始化：将整段空间作为一个空闲块
    explicit FreeList(std::size_t total) {
        freeBlocks_.push_back({0, total});
    }

    // 分配：首次适配（First-Fit）
    // 成功：返回 true，并在 outOffset 中写入起始偏移
    // 失败：返回 false，不改变 outOffset
    bool allocate(std::size_t size, std::size_t& outOffset) {
        for (auto it = freeBlocks_.begin(); it != freeBlocks_.end(); ++it) {
            if (it->size >= size) {
                outOffset = it->offset;
                if (it->size == size) {
                    // 刚好用尽该空闲块
                    freeBlocks_.erase(it);
                } else {
                    // 从前部切走 size 字节
                    it->offset += size;
                    it->size   -= size;
                }
                return true;
            }
        }
        return false;
    }

    // 释放：按 offset 升序插入，并与前后相邻块合并
    void deallocate(std::size_t offset, std::size_t size) {
        auto it = freeBlocks_.begin();
        for (; it != freeBlocks_.end() && it->offset < offset; ++it) {}
        auto inserted = freeBlocks_.insert(it, {offset, size});
        coalesce(inserted);
    }

    // 打印空闲块分布
    void dump() const {
        std::cout << "Free blocks:";
        for (const auto& b : freeBlocks_) {
            std::cout << " [" << b.offset << "," << b.size << "]";
        }
        std::cout << '\n';
    }

private:
    // 与相邻块（前/后）合并
    void coalesce(std::list<Block>::iterator it) {
        // 与前一个相邻块合并
        if (it != freeBlocks_.begin()) {
            auto prev = std::prev(it);
            if (prev->offset + prev->size == it->offset) {
                prev->size += it->size;
                it = freeBlocks_.erase(it);
                it = prev;
            }
        }
        // 与后一个相邻块合并
        auto next = std::next(it);
        if (next != freeBlocks_.end() && it->offset + it->size == next->offset) {
            it->size += next->size;
            freeBlocks_.erase(next);
        }
    }

    std::list<Block> freeBlocks_; // 按 offset 升序的空闲块列表
};

int main() {
    FreeList allocator(1024);
    allocator.dump();

    std::size_t a, b;
    allocator.allocate(128, a);
    allocator.allocate(256, b);
    std::cout << "Allocated blocks at " << a << " (128) and " << b << " (256)\n";
    allocator.dump();

    allocator.deallocate(a, 128);
    allocator.dump();

    allocator.deallocate(b, 256);
    allocator.dump();

    allocator.allocate(512, a);
    std::cout << "Allocated 512 at " << a << '\n';
    allocator.dump();
    return 0;
}